# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        # m = []
        # p = head
        # while p:
        #     v = p.val
        #     m.append(v)
        #     p=p.next
        # m = list(reversed(m))
        # h1 = h = ListNode(None)
        # for i in m:
        #     h.next = ListNode(i)
        #     h = h.next
        # h.next= ListNode(None)
        # return h1.next


# 尾插法
        tmp_Node = ListNode(-1)
        while head:
            next = head.next
            head.next = tmp_Node.next
            tmp_Node.next = head
            head = next
        return tmp_Node.next
        # p = ListNode(None)
        # p.next = head
        # while head:
        #     p.next = head.next
        #     head.next = p.next.next
        #     p.next.next = head
        # return p.next



l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(3)
l1.next.next.next = ListNode(4)

m = Solution()
s = m.reverseList(l1)

while s!= None:
    print(s.val)
    s = s.next